package com.jinan.algorithm;

import java.util.*;

public class Test {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Test test = new Test();
        System.out.println(test.decodeString("3[a]2[bc]"));
    }


    /**
     * 554.砖墙
     *
     * @param wall
     * @return
     */
    public int leastBricks(List<List<Integer>> wall) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (List<Integer> row : wall) {
            int gap = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                gap += row.get(i);
                if (map.containsKey(gap)) {
                    map.put(gap, map.get(gap) + 1);
                } else {
                    map.put(gap, 1);
                }
            }
        }
        int max = 0;
        for (Integer key : map.keySet()) {
            max = Math.max(max, map.get(key));
        }
        return wall.size() - max;
    }

    /**
     * 15.三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
     * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。
     * 请你返回所有和为 0 且不重复的三元组。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n - 2; i++) {
            int t = nums[i];
            if (i > 0 && nums[i - 1] == t) {
                continue;
            }
            if (t + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            if (t + nums[n - 2] + nums[n - 1] < 0) {
                continue;
            }
            int j = i + 1, k = n - 1;
            while (j < k && j < n && k < n) {
                int sum = nums[j] + nums[k] + t;
                if (sum == 0) {
                    list.add(Arrays.asList(t, nums[j], nums[k]));
                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }

                } else if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return list;
    }

    /**
     * 维护一个操作优先级
     */
    Map<Character, Integer> map = new HashMap<>() {
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }
    };

    /**
     * 227.基本计算器 II
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * 整数除法仅保留整数部分。
     * 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
     *
     * @param s
     * @return
     */
    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        Deque<Integer> num = new ArrayDeque<>();
        num.addLast(0);
        Deque<Character> op = new ArrayDeque<>();
        int ret = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                op.addLast(c);
            } else if (c == ')') {
                while (!op.isEmpty()) {
                    if (op.peekLast() != '(') {
                        compute(num, op);
                    } else {
                        op.pollLast();
                        break;
                    }
                }
            } else {
                if (Character.isDigit(c)) {
                    int currentNum = 0;
                    while (i < s.length() && Character.isDigit(s.charAt(i))) {
                        currentNum = currentNum * 10 + (s.charAt(i) - '0');
                        i++;
                    }
                    num.addLast(currentNum);
                    i--;
                } else {
                    if (i > 0 && (s.charAt(i - 1) == '(' || s.charAt(i - 1) == '+' || s.charAt(i - 1) == '-')) {
                        num.addLast(0);
                    }
                    while (!op.isEmpty() && op.peekLast() != '(' && map.get(op.peekLast()) >= map.get(c)) {
                        compute(num, op);
                    }
                    op.addLast(c);
                }
            }
        }
        while (!op.isEmpty()) {
            compute(num, op);
        }
        return num.peekLast();
    }

    public void compute(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.size() < 2) return;
        if (ops.isEmpty()) return;
        char operator = ops.pollLast();
        int y = nums.pollLast();
        int x = nums.pollLast();
        int ans = 0;
        if (operator == '+') {
            ans = x + y;
        } else if (operator == '-') {
            ans = x - y;
        } else if (operator == '*') {
            ans = x * y;
        } else if (operator == '/') {
            ans = x / y;
        } else if (operator == '^') {
            ans = (int) Math.pow(x, y);
        } else if (operator == '%') {
            ans = x % y;
        }
        nums.addLast(ans);
    }

    /**
     * 56.合并区间
     * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> ans = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });
        for (int[] interval : intervals) {
            int m = ans.size();
            if (m > 0 && ans.get(m - 1)[1] >= interval[0]) {
                ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], interval[1]);
            } else {
                ans.add(interval);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

    /**
     * 394.字符串解码
     *
     * @param s
     * @return
     */
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        Deque<Integer> stack_multi = new LinkedList<>();
        Deque<String> stack_res = new LinkedList<>();
        for (Character c : s.toCharArray()) {
            if (c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.pollLast();
                tmp.append(String.valueOf(res).repeat(Math.max(0, cur_multi)));
                res = new StringBuilder(stack_res.pollLast() + tmp);
            } else if (c >= '0' && c <= '9') {
                multi = multi * 10 + c - '0';
            } else res.append(c);
        }
        return res.toString();
    }

    /**
     * 415.字符串相加
     * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
     * <p>
     * 注意：
     * num1 和num2 的长度都小于 5100.
     * num1 和num2 都只包含数字 0-9.
     * num1 和num2 都不包含任何前导零。
     * 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
     *
     * @param num1
     * @param num2
     */
    public String addStrings(String num1, String num2) {
        // 从低位开始相加
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        // 进位
        int carry = 0;
        // 结果
        StringBuilder res = new StringBuilder();
        // 从低位开始相加
        while (n1 >= 0 || n2 >= 0) {
            int x1 = n1 >= 0 ? num1.charAt(n1) - '0' : 0;
            int x2 = n2 >= 0 ? num2.charAt(n2) - '0' : 0;
            int sum = x1 + x2 + carry;
            res.append(sum % 10);
            carry = sum / 10;
            n1--;
            n2--;
        }
        if (carry > 0) {
            res.append(carry);
        }
        return res.reverse().toString();
    }

    /**
     * 402.移掉K位数字
     * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
     * 注意:
     * num 的长度小于 10002 且 ≥ k。
     * num 不会包含任何前导零。
     *
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        Deque<Character> stack = new LinkedList<>();
        for (char c : num.toCharArray()) {
            while (!stack.isEmpty() && stack.peekLast() > c && k > 0) {
                stack.pollLast();
                k--;
            }
            stack.addLast(c);
        }
        while (k > 0) {
            stack.pollLast();
            k--;
        }
        StringBuilder res = new StringBuilder();
        boolean leadingZero = true;
        while (!stack.isEmpty()) {
            char c = stack.pollFirst();
            if (leadingZero && c == '0') {
                continue;
            }
            leadingZero = false;
            res.append(c);
        }
        return res.isEmpty() ? "0" : res.toString();
    }

    /**
     * 316.去除重复字母
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
     * 需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     *
     * @param s
     * @return
     */
    public String removeDuplicateLetters(String s) {
        int n = s.length();
        Deque<Character> stack = new LinkedList<>();
        boolean[] inStack = new boolean[26];
        int[] count = new int[26];
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']++;
        }
        for (char c : s.toCharArray()) {
            count[c - 'a']--;
            if (inStack[c - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peekLast() > c && count[stack.peekLast() - 'a'] > 0) {
                inStack[stack.peekLast() - 'a'] = false;
                stack.pollLast();
            }
            stack.addLast(c);
            inStack[c - 'a'] = true;
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pollFirst());
        }
        return res.toString();
    }

    /**
     * 5.最长回文子串
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0;
        int end = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j < 3) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                    if (dp[j][i] && i - j > end - start) {
                        start = j;
                        end = i;
                    }
                } else {
                    dp[j][i] = false;
                }
            }
        }
        return s.substring(start, end + 1);
    }


    /**
     * 647.回文子串
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j < 3) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                } else dp[j][i] = false;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[j][i]) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 53.最大子序和
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int res=nums[0];
        int[] dp=new int[n];
        dp[0]=nums[0];
        for (int i = 1; i < n; i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            res=Math.max(res,dp[i]);
        }
        return res;
    }

    /**
     * 322.零钱兑换
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
     * 你可以认为每种硬币的数量是无限的。
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i=0;i<=amount;i++){
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];

//        int n = coins.length;
//        int[] dp = new int[amount + 1];
//        Arrays.fill(dp, amount + 1);
//        dp[0] = 0;
//        for (int coin : coins) {
//            for (int j = coin; j <= amount; j++) {
//                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
//            }
//        }
//        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

}


